//
//  KMP.cpp
//  第四章习题for Xcode
//
//  Created by asus on 2020/7/5.
//  Copyright © 2020 唐沈飞. All rights reserved.
//

#include "KMP.hpp"

//计算出next数组
void GetNext(STR substr, int next[])
{
    int i = 1, j = 0;
    next[1] = 0;
    while (i < substr.length)
    {
        if(j == 0 || substr.str[i] == substr.str[j])
        {
            ++i;
            ++j;
            next[i] = j;
        }
        else
            j = next[j];
    }
}

//改进KMP算法，减少重复步骤，计算出nextval数组
void GetNextVal(STR substr, int nextval[])
{
    int i = 1, j = 0;
    nextval[1] = 0;
    while (i < substr.length)
    {
        if(j == 0 || substr.str[i] == substr.str[j])
        {
            ++i;
            ++j;
            //不匹配直接t跳回正确位置，不必依次比较回溯
            if(substr.str[i] != substr.str[j])
                nextval[i] = j;
            else
                nextval[i] = nextval[j];
        }
        else
            j = nextval[j];
    }
}

//KMP算法
int KMP(STR str, STR substr, int next[])
{
    int i = 1, j = 1;
    while (i <= str.length && j <= substr.length)
    {
        if(j == 0 || str.str[i] == substr.str[j])
        {
            ++i;
            ++j;
        }
        else
        {
            j = next[j];    //比较失败则按照next数组直接回到h正确的位置
        }
    }
    if(j > substr.length)
        return i - substr.length;
    else
        return 0;
}
